<?php

/**
 * 快速排序
 *
 * @param $arr
 *
 * @return array
 */
function QuickSort($arr)
{
    $count = count($arr);
    
    if ($count < 2)
    {
        return $arr;
    }
    //使用随机种子解决数组有序退化为o(n^2)的情况
    $key = mt_rand(0,$count-1);
    list($arr[0],$arr[$key]) = array($arr[$key],$arr[0]);
    $left = $right = [];
    
    $tmp = $arr[0];
    for ($i=1;$i<$count;$i++)
    {
        if ($tmp>$arr[$i])
        {
            $left[] = $arr[$i];
        }
        else
        {
            $right[] = $arr[$i];
        }
    }
    $left  = QuickSort($left);
    $right = QuickSort($right);
    
    $arr = array_merge($left,[$tmp],$right);
    return $arr;
}

$arr = [1,2,3,43,121,12,-2,1,3,0.2,121,342];
for($i=0;$i<20000;$i++)
{
    $arr[] = mt_rand(0,10000);
}
$before_time = microtime(true);
var_dump(QuickSort($arr));
$after_time = microtime(true);
$time = round($after_time-$before_time,3);
echo '耗时'.$time.'秒';
